package com.leetcode.no102;

import java.lang.reflect.Array;
import java.util.*;

/**
 * Definition for a binary tree node.
 */

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {
//    private Queue<TreeNode> nodesQueue;
//    private List<List<Integer>> result;


    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return null;
        }

        // 队列
        Queue<TreeNode> nodeQueue = new ArrayDeque<TreeNode>();

        // 结果
        List<List<Integer>> result = new ArrayList<List<Integer>>();

        // 插入队尾
        nodeQueue.offer(root);


        // 不为空的时候就...
        while (!nodeQueue.isEmpty()) {
            int n = nodeQueue.size();
            List<Integer> level = new ArrayList<Integer>();

            // 当前这一层
            for (int i = 0; i < n; i++) {
                // 队头取
                TreeNode tmpNode = nodeQueue.poll();

                level.add(tmpNode.val);

                if (tmpNode.left != null) {
                    nodeQueue.offer(tmpNode.left);
                }

                if (tmpNode.right != null) {
                    nodeQueue.offer(tmpNode.right);
                }

            }
            result.add(level);

        }

        // 返回结果
        return result;
    }

}